#include <stdio.h>
//图的应用之最短路径之迪杰斯特拉算法
#define MAXSIZE 100
#define MAX 0x10000
typedef struct 
{
    int vertex[MAXSIZE];//因为顶点是v0,v1这样的形式，所以我们只存下标，打印时写成"V%d"即可
    int edge[MAXSIZE][MAXSIZE];
    int vertex_num;
    int edge_num;
}mat_graph;
void creatgraph(mat_graph *g)
{
    g->vertex_num=9;
    g->edge_num=16;
    int i,j;
    for(i=0;i<g->vertex_num;i++)
    {
        g->vertex[i]=i;
    }
    for(i=0;i<g->vertex_num;i++)
    {
        for(j=0;j<g->vertex_num;j++)
        {
            if(i==j)
            g->edge[i][j]=0;
            else
            g->edge[i][j]=MAX;
        }
    }
    g->edge[0][1]=1;
    g->edge[0][2]=5;
    g->edge[1][2]=3;
    g->edge[1][3]=7;
    g->edge[1][4]=5;
    g->edge[2][4]=1;
    g->edge[2][5]=7;
    g->edge[3][4]=2;
    g->edge[3][6]=3;
    g->edge[4][5]=3;
    g->edge[4][6]=6;
    g->edge[4][7]=9;
    g->edge[5][7]=5;
    g->edge[6][7]=2;
    g->edge[6][8]=7;
    g->edge[7][8]=4;
    for(i=0;i<g->vertex_num;i++)
    {
        for(j=0;j<i;j++)
        {
            g->edge[i][j]=g->edge[j][i];
        }
    }
}
int choose(int distance[],int found[],mat_graph *g) 
{
    int min=MAX;
    int i,k;
    for(i=1;i<g->vertex_num;i++)
    {
        if(distance[i]<min&&found[i]==0)
        {
            min=distance[i];
            k=i;
        }
    }
    return k;
}
void Dijkstra(mat_graph *g,int begin)
{
    int found[MAXSIZE]={0};//存放顶点是否走过的信息，类似于30中的visited数组
    //因为这个算法是在找v0到每个顶点的最短路径，所以当找完一个顶点后要记录下来，然后再找其他的顶点，这样才不会重复
    int path[MAXSIZE];//路径，path数组下标就是顶点下标，存放下标对应的顶点的最近的顶点下标
    //其实就是下标代表“一个顶点”，这个下标对应的数组中存放另一个顶点的下标，这个“另一个顶点”就是离“一个顶点”最近的顶点
    //找最短路径就是反推，每次找离自己最近的顶点直到找到起点，这些顶点连成的边就是最短路径
    int distance[MAXSIZE];//存放起点到每个顶点的最短路径的权值，也就是begin到每个顶点的最短距离
    //初始化上面的数组
    int i,j;
    for(i=0;i<g->vertex_num;i++)
    {
        path[i]=-1; //不赋值为0，是因为0在数组中有意义，代表起点
        distance[i]=g->edge[begin][i]; //begin到每个顶点的最短距离
    }
    found[begin]=1;
    int next; //要找最短路径的下一个顶点
    for(i=1;i<g->vertex_num;i++) //i=1是因为除去起点
    {
        next=choose(distance,found,g);
        found[next]=1;
        for(j=0;j<g->vertex_num;j++)
        {
            if(distance[next]+g->edge[next][j]<distance[j]&&found[j]==0)
            {
                distance[j]=distance[next]+g->edge[next][j];
                path[j]=next;
            }
        }
    }
    for(i=1;i<g->vertex_num;i++)
    {
        printf("v0->v%d:%d\n",i,distance[i]);
        j=i;
        printf("v%d<-",j);
        while(path[j]!=-1)
        {
            printf("v%d<-",path[j]);
            j=path[j];
        }
        printf("v0\n");
    }
}
int main()
{
    mat_graph g;
    creatgraph(&g);
    int begin=0; //因为这种算法是从v0出发，找其余每个点的最短路径，都是v0到vn，所以要把起点传过去，这里我们传下标
    Dijkstra(&g,begin);
    return 0;
}

/*
v0->v1:1
v1<-v0
v0->v2:4
v2<-v1<-v0
v0->v3:7
v3<-v4<-v2<-v1<-v0
v0->v4:5
v4<-v2<-v1<-v0
v0->v5:8
v5<-v4<-v2<-v1<-v0
v0->v6:10
v6<-v3<-v4<-v2<-v1<-v0
v0->v7:12
v7<-v6<-v3<-v4<-v2<-v1<-v0
v0->v8:16
v8<-v7<-v6<-v3<-v4<-v2<-v1<-v0
*/